package com.huangpeng.algorithm.dataStructure;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author huangpeng
 * @Title 深度优先和广度优先搜索算法
 * @Package
 * @Date 2021/7/20 14:10
 * @Description 无向图
 * @Version 1.0
 */
public class Graph {
    private int v;//顶点个数
    private LinkedList<Integer> adj[];//邻接表
    boolean found = false; // 全局变量或者类成员变量

    public Graph(int v){
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    /**
     * 无向图一条边存两次
     * @param s
     * @param t
     */
    public void addEdge(int s,int t){
        adj[s].add(t);
        adj[t].add(s);
    }

    /**
     * 广度优先搜索（BFS）
     * @param s
     * @param t
     */
    public void bfs(int s,int t){
        if(s == t){
            return;
        }
        boolean[] visited = new boolean[v];
        visited[s] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        int[] prev = new int[v];
        for (int i = 0; i < v; i++) {
            prev[i] = -1;
        }
        while(queue.size() != 0){
            int w = queue.poll();
            for (int i = 0; i < adj[w].size(); i++) {
                int q = adj[w].get(i);
                if(!visited[q]){
                    prev[q] = w;
                    if(q == t){
                        prints(prev,s,t);
                        return;
                    }
                    visited[q] = true;
                    queue.add(q);
                }
            }
        }
    }

    /**
     * 递归打印 s->t 的路径
     * @param prev
     * @param s
     * @param t
     */
    public void prints(int[] prev, int s, int t) {
        if(prev[t] != -1 && t != s){
            prints(prev,s,prev[t]);
        }
        System.out.println(t + " ");
    }

    /**
     * 深度优先搜索（DFS）
     * @param s
     * @param t
     */
    public void dfs(int s,int t){
        found = false;
        boolean[] visited = new boolean[v];
        int[] prev = new int[v];
        for (int i = 0; i < v; i++) {
            prev[i] = -1;
        }
        recurDfs(s,t,visited,prev);
        prints(prev,s,t);
    }

    private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
        if(found == true){
            return;
        }
        visited[w] = true;
        if(w == t){
            found = true;
            return;
        }
        for (int i = 0; i < adj[w].size(); i++) {
            int q = adj[w].get(i);
            if(!visited[q]){
                prev[q] = w;
                recurDfs(q,t,visited,prev);
            }
        }
    }

    /**
     * Kahn 算法用代码实现
     */
    public void topoSortByKahn(){
        int[] inDegree = new int[v];
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < adj[i].size(); j++) {
                int w = adj[i].get(j);// i->w
                inDegree[w] ++;
            }
        }
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < v; i++) {
            if(inDegree[i] == 0){
                queue.add(i);
            }
        }
        while(!queue.isEmpty()){
            int i = queue.remove();
            System.out.print("->" + i);
            for (int j = 0; j < adj[i].size(); j++) {
                int k = adj[i].get(j);
                inDegree[k] --;
                if(inDegree[k] == 0){
                   queue.add(k);
                }
            }
        }
    }

    /**
     * DFS 算法实现
     */
    public void topoSortByDFS(){
        // 先构建逆邻接表，边 s->t 表示，s 依赖于 t，t 先于 s
        LinkedList<Integer> inverseAdj[] = new LinkedList[v];
        for (int i = 0; i < v; i++) {// 申请空间
            inverseAdj[i] = new LinkedList<>();
        }
        // 通过邻接表生成逆邻接表
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < adj[i].size(); j++) {
                int w = adj[i].get(j);// i->w
                inverseAdj[w].add(i);// w->i
            }
        }
        boolean[] visited = new boolean[v];//是否被搜索过
        for (int i = 0; i < v; i++) {// 深度优先遍历图
            if(visited[i] = false){
                visited[i] = true;
                dfs(i,inverseAdj,visited);
            }

        }

    }

    /**
     * 深度优先搜索（DFS）
     * @param vertex
     * @param inverseAdj
     * @param visited
     */
    public void dfs(int vertex, LinkedList<Integer> inverseAdj[], boolean[] visited){
        for (int i = 0; i < inverseAdj[vertex].size(); i++) {
            int w = inverseAdj[vertex].get(i);
            if(visited[w] = true){
                continue;
            }
            visited[w] = true;
            dfs(w,inverseAdj,visited);
        }
        // 先把 vertex 这个顶点可达的所有顶点都打印出来之后，再打印它自己
        System.out.print("->" + vertex);
    }

    public static void main(String[] args) {
        Graph graph = new Graph(20);
        graph.addEdge(0,19);
        graph.bfs(6,15);
        graph.topoSortByDFS();
        graph.topoSortByDFS();
    }
}
